package homework;

import java.util.HashMap;
import java.util.Map;

//作业标题(2714)
//复杂链表的复制
//
//作业内容
//复杂链表的复制
//https://leetcode.cn/problems/copy-list-with-random-pointer/description/
public class h2714 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList1(Node head) {
        if(head == null) return null;
        Node cur = head;
        while(cur != null)
        {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = cur.next.next;
        }

        cur = head;
        while (cur != null )
        {
            if(cur.random != null)
            {
                cur.next.random = cur.random.next;
            }
            else
            {
                cur.next.random = null;
            }

            cur = cur.next.next;
        }

        cur = head;
        Node ret = head.next;
        while(cur != null )
        {
            Node nodeNew = cur.next;
            cur.next = cur.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
            cur = cur.next;
        }

        return ret;
    }
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null)
        {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        for(Map.Entry<Node, Node> node : map.entrySet())
        {
            node.getValue().next = map.get(node.getKey().next);
            node.getValue().random = map.get(node.getKey().random);
        }
        return map.get(head);
    }
}
